home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / util / pathnode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-05  |  16.7 KB  |  576 lines
  1. /*     
  2.  *      FILE
  3.  *         pathnode
  4.  *     
  5.  *      DESCRIPTION
  6.  *         Routines to manipulate pathlists and create path nodes
  7.  *     
  8.  *      EXPORTS
  9.  *             path-is-cheaper
  10.  *             cheaper-path
  11.  *             set_cheapest
  12.  *             add_pathlist
  13.  *             create_seqscan_path
  14.  *             create_index_path
  15.  *             create_nestloop_path
  16.  *             create_mergesort_path
  17.  *             create_hashjoin_path
  18.  *    $Header: /private/postgres/src/planner/util/RCS/pathnode.c,v 1.25 1992/07/15 00:40:22 joey Exp $
  19.  */
  20. #include <math.h>
  21.  
  22. #include "planner/internal.h"
  23.  
  24. #include "nodes/relation.h"
  25. #include "nodes/relation.a.h"
  26. #include "utils/log.h"
  27.  
  28. #include "planner/pathnode.h"
  29. #include "planner/clauseinfo.h"
  30. #include "planner/cfi.h"
  31. #include "planner/costsize.h"
  32. #include "planner/keys.h"
  33. #include "planner/xfunc.h"
  34.  
  35. /* for set_clause_selectivities() */
  36. #include "planner/clausesel.h"
  37.  
  38. extern int testFlag;
  39.  
  40. /*        ====================
  41.  *        MISC. PATH UTILITIES
  42.  *        ====================
  43.  */
  44.  
  45. /*    
  46.  *        path-is-cheaper
  47.  *    
  48.  *        Returns t iff 'path1' is cheaper than 'path2'.
  49.  *    
  50.  */
  51.  
  52. /*  .. best-innerjoin, better_path, cheaper-path, match-unsorted-outer
  53.  *  .. set_cheapest
  54.  */
  55. bool
  56. path_is_cheaper (path1,path2)
  57.      Path path1,path2 ;
  58. {
  59.     Cost cost1 = get_path_cost (path1);
  60.     Cost cost2 = get_path_cost (path2);
  61.  
  62.     return((bool)(cost1 < cost2));
  63. }
  64.  
  65. /*    
  66.  *        cheaper-path
  67.  *    
  68.  *        Returns the cheaper of 'path1' and 'path2'.
  69.  *    
  70.  */
  71. Path
  72. cheaper_path (path1,path2)
  73.      Path path1,path2 ;
  74. {
  75.     if ( null(path1) || null (path2) ) {
  76.     elog (WARN,"cheaper-path: bad path");
  77.     } 
  78.     if ( path_is_cheaper (path1,path2) ) {
  79.     return(path1);
  80.     } 
  81.     else {
  82.     return(path2);
  83.     } 
  84. }
  85.  
  86. /*    
  87.  *        set_cheapest
  88.  *    
  89.  *        Finds the minimum cost path from among a relation's paths.  
  90.  *    
  91.  *        'parent-rel' is the parent relation
  92.  *        'pathlist' is a list of path nodes corresponding to 'parent-rel'
  93.  *    
  94.  *        Returns    and sets the relation entry field with the pathnode that 
  95.  *        is minimum.
  96.  *    
  97.  */
  98.  
  99. /*  .. prune-rel-path, set_cheapest, sort-relation-paths
  100.  */
  101.  
  102. Path
  103. set_cheapest (parent_rel,pathlist)
  104.      Rel parent_rel;
  105.      List pathlist ;
  106. {
  107.      List temp_path;
  108.      Path cheapest_so_far;
  109.  
  110.      Assert(consp(pathlist));
  111.      Assert(IsA(parent_rel,Rel));
  112.  
  113.      cheapest_so_far = (Path)CAR(pathlist);
  114.  
  115.      foreach (temp_path,CDR(pathlist)) {
  116.      Path path = (Path)CAR(temp_path);
  117.      cheapest_so_far = cheaper_path(path,cheapest_so_far);
  118.      }
  119.  
  120.      set_cheapestpath (parent_rel,(PathPtr)cheapest_so_far);
  121.  
  122.      return(cheapest_so_far);
  123. }
  124.  
  125. /*    
  126.  *        add_pathlist
  127.  *    
  128.  *        For each path in the list 'new-paths', add to the list 'unique-paths' 
  129.  *        only those paths that are unique (i.e., unique ordering and ordering 
  130.  *        keys).  Should a conflict arise, the more expensive path is thrown out,
  131.  *        thereby pruning the plan space.
  132.  *    
  133.  *        'parent-rel' is the relation entry to which these paths correspond.
  134.  *    
  135.  *        Returns the list of unique pathnodes.
  136.  *    
  137.  */
  138.  
  139. /*  .. find-all-join-paths, find-rel-paths, prune-joinrel
  140.  */
  141. LispValue
  142. add_pathlist (parent_rel,unique_paths,new_paths)
  143.      Rel parent_rel;
  144.      List unique_paths,new_paths ;
  145. {
  146.      LispValue x;
  147.      Path new_path;
  148.      LispValue old_path;
  149.      foreach (x, new_paths) {
  150.      new_path = (Path)CAR(x);
  151.      if (member((LispValue)new_path, unique_paths)) 
  152.          continue;
  153.      old_path = better_path (new_path,unique_paths);
  154.      if (old_path == LispTrue) {
  155.          /*  Is a brand new path.  */
  156.          set_parent (new_path,parent_rel);
  157.          unique_paths = lispCons ((LispValue)new_path,unique_paths);
  158.     
  159.      }
  160.      else if (null(old_path))
  161.        ;  /* do nothing if path is not cheaper */
  162.      else if (IsA(old_path,Path)) {
  163.          set_parent (new_path,parent_rel);
  164.          if (testFlag) {
  165.              unique_paths = lispCons((LispValue)new_path, unique_paths);
  166.         }
  167.          else
  168.              unique_paths = lispCons((LispValue)new_path,
  169.                          LispRemove(old_path,unique_paths));
  170.      }
  171.      }
  172.      return(unique_paths);
  173.  }
  174.  
  175. /*    
  176.  *        better_path
  177.  *    
  178.  *        Determines whether 'new-path' has the same ordering and keys as some 
  179.  *        path in the list 'unique-paths'.  If there is a redundant path,
  180.  *        eliminate the more expensive path.
  181.  *    
  182.  *        Returns:
  183.  *        The old path - if 'new-path' matches some path in 'unique-paths' and is
  184.  *            cheaper
  185.  *        nil - if 'new-path' matches but isn't cheaper
  186.  *        t - if there is no path in the list with the same ordering and keys
  187.  *    
  188.  */
  189.  
  190. /*  .. add_pathlist    */
  191.  
  192. LispValue
  193. better_path (new_path,unique_paths)
  194.      Path new_path;
  195.      List unique_paths ;
  196. {
  197.      Path old_path = (Path)NULL;
  198.      Path path = (Path)NULL;
  199.      LispValue temp = LispNil;
  200.      LispValue retval = LispNil;
  201.  
  202.      /* XXX - added the following two lines which weren't int
  203.     the lisp planner, but otherwise, doesn't seem to work
  204.     for the case where new_path is 'nil */
  205.      
  206.      foreach (temp,unique_paths) {
  207.      path = (Path) CAR(temp);
  208.      if ((equal_path_path_ordering (get_p_ordering (new_path),
  209.                     get_p_ordering(path)) &&
  210.           samekeys (get_keys (new_path),get_keys (path)))) {
  211.          old_path = path;
  212.          break;
  213.      }
  214.      }
  215.      if ( null(old_path)) {
  216.      retval = LispTrue;
  217.      } 
  218.      else 
  219.        if (path_is_cheaper (new_path,old_path) || testFlag) {
  220.        retval = (LispValue)old_path;
  221.        } 
  222.        else
  223.      retval = LispNil;
  224.      
  225.      return(retval);
  226. }
  227.  
  228.  
  229.  
  230. /*        ===========================
  231.  *        PATH NODE CREATION ROUTINES
  232.  *        ===========================
  233.  */
  234.  
  235. /*    
  236.  *        create_seqscan_path
  237.  *    
  238.  *        Creates a path corresponding to a sequential scan, returning the
  239.  *        pathnode.
  240.  *    
  241.  */
  242.  
  243. /*  .. find-rel-paths
  244.  */
  245. Path
  246. create_seqscan_path (rel)
  247.      Rel rel ;
  248. {
  249.     LispValue relid;
  250.  
  251.     Path pathnode = RMakePath();
  252.  
  253.     set_pathtype (pathnode,T_SeqScan); 
  254.     set_parent (pathnode,rel);
  255.     set_path_cost (pathnode,0.0);
  256.     set_p_ordering (pathnode,LispNil);
  257.     set_pathsortkey (pathnode,(SortKey)NULL);
  258.     set_keys (pathnode,LispNil);
  259.     /* copy clauseinfo list into path for expensive function processing 
  260.         -- JMH, 7/7/92 */
  261.     set_locclauseinfo(pathnode,
  262.               (List)CopyObject(get_clauseinfo(rel)));
  263.  
  264.     relid = get_relids(rel);
  265.     if (!null(relid))
  266.       relid = CAR(relid);
  267.  
  268.     set_path_cost (pathnode,cost_seqscan (relid,
  269.                       get_pages (rel),get_tuples (rel)));
  270.     /* add in expensive functions cost!  -- JMH, 7/7/92 */
  271.     set_path_cost(pathnode, 
  272.           (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  273.     return(pathnode);
  274. }
  275.  
  276. /*    
  277.  *        create_index_path
  278.  *    
  279.  *        Creates a single path node for an index scan.
  280.  *    
  281.  *        'rel' is the parent rel
  282.  *        'index' is the pathnode for the index on 'rel'
  283.  *        'restriction-clauses' is a list of restriction clause nodes.
  284.  *        'is-join-scan' is a flag indicating whether or not the index is being
  285.  *            considered because of its sort order.
  286.  *    
  287.  *        Returns the new path node.
  288.  *    
  289.  */
  290.  
  291.  
  292. /*  .. create-index-paths, find-index-paths
  293.  */
  294.  
  295. IndexPath
  296. create_index_path (rel,index,restriction_clauses,is_join_scan)
  297.      Rel rel,index;
  298.      LispValue restriction_clauses;
  299.      bool is_join_scan;
  300. {
  301.     IndexPath pathnode = RMakeIndexPath();
  302.     
  303.     set_pathtype ((Path)pathnode,T_IndexScan);
  304.     set_parent ((Path)pathnode,rel);
  305.     set_indexid (pathnode,get_relids (index));
  306.     set_p_ordering ((Path)pathnode,get_ordering (index));
  307.     set_keys ((Path)pathnode,get_indexkeys (index));
  308.     set_pathsortkey((Path)pathnode, (SortKey)NULL);
  309.     set_indexqual(pathnode, LispNil);
  310.     /* copy clauseinfo list into path for expensive function processing 
  311.        -- JMH, 7/7/92 */
  312.     set_locclauseinfo(pathnode,
  313.               set_difference(CopyObject(get_clauseinfo(rel)),
  314.                      restriction_clauses /* ,
  315.                      LispNil (arg too much - kai) */));
  316.  
  317.     /*    The index must have an ordering for the
  318.       path to have (ordering) keys, 
  319.       and vice versa. */
  320.      
  321.     if ( get_p_ordering ((Path)pathnode)) {
  322.     set_keys ((Path)pathnode,collect_index_pathkeys( get_indexkeys (index),
  323.                              get_targetlist (rel)));
  324.        /*    Check that the keys haven't 'disappeared', since they may 
  325.          no longer be in the target list (i.e.,
  326.          index keys that are not 
  327.          relevant to the scan are not applied to the scan path node,
  328.          so if no index keys were found, we can't order the path). */
  329.  
  330.        if ( null (get_keys ((Path)pathnode))) {
  331.            set_p_ordering ((Path)pathnode,LispNil);
  332.        }
  333.     }
  334.     if(is_join_scan || null (restriction_clauses)) {
  335.     /*    Indices used for joins or sorting result nodes don't
  336.           restrict the result at all, they simply order it,
  337.           so compute the scan cost 
  338.           accordingly -- use a selectivity of 1.0. */
  339.     set_path_cost ( (Path)pathnode,
  340.             cost_index (CInteger(CAR(get_relids(index))),
  341.                     get_pages (index),1.0,
  342.                     get_pages (rel),
  343.                     get_tuples (rel),
  344.                     get_pages (index),
  345.                     get_tuples(index), false));
  346.     /* add in expensive functions cost!  -- JMH, 7/7/92 */
  347.     set_path_cost(pathnode, 
  348.               (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  349.     } 
  350.     else  {
  351.     /*    Compute scan cost for the case when 'index' is used with a 
  352.           restriction clause. */
  353.     LispValue relattvals = get_relattvals (restriction_clauses);
  354.     /* pagesel is '(Cost Cost) */
  355.     List pagesel = index_selectivity (CInteger(CAR(get_relids(index))),
  356.                       get_classlist (index),
  357.                       get_opnos (restriction_clauses),
  358.                       CInteger(getrelid (CInteger
  359.                             (CAR(get_relids (rel))),
  360.                             _query_range_table_)),
  361.                       nth (0,relattvals),
  362.                       nth (1,relattvals),
  363.                       nth (2,relattvals),
  364.                       length (restriction_clauses));
  365.     /*   each clause gets an equal selectivity */
  366.     Cost clausesel = 
  367.       pow (CDouble(CADR (pagesel)),
  368.            (double)(1/length(restriction_clauses)));
  369.      
  370.     Count temp1 = (Count)CDouble(CAR(pagesel));
  371.     Cost temp2 = (Cost)CDouble(CADR(pagesel));
  372.  
  373.     set_indexqual (pathnode,restriction_clauses);
  374.     set_path_cost ( (Path)pathnode,
  375.             cost_index (CInteger(CAR(get_relids(index))),
  376.                      temp1,
  377.                     temp2,
  378.                     get_pages (rel),
  379.                     get_tuples (rel),get_pages (index),
  380.                     get_tuples (index), false));
  381.     /* add in expensive functions cost!  -- JMH, 7/7/92 */
  382.     set_path_cost(pathnode, 
  383.               (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  384.  
  385.     /*    Set selectivities of clauses used with index to 
  386.           the selectivity of this index, subdividing the 
  387.           selectivity equally over each of 
  388.           the clauses. 
  389.           */
  390.     /*    XXX Can this divide the selectivities in a better way? */
  391.     
  392.     set_clause_selectivities (restriction_clauses,clausesel);
  393.     }
  394.     return(pathnode);
  395. }
  396.  
  397. /*    
  398.  *        create_nestloop_path
  399.  *    
  400.  *        Creates a pathnode corresponding to a nestloop join between two 
  401.  *        relations.
  402.  *    
  403.  *        'joinrel' is the join relation.
  404.  *        'outer_rel' is the outer join relation
  405.  *        'outer_path' is the outer join path.
  406.  *        'inner_path' is the inner join path.
  407.  *        'keys' are the keys of the path
  408.  *        
  409.  *        Returns the resulting path node.
  410.  *    
  411.  */
  412.  
  413. /*  .. match-unsorted-outer
  414.  */
  415. JoinPath
  416. create_nestloop_path (joinrel,outer_rel,outer_path,inner_path,keys)
  417.      Rel joinrel,outer_rel;
  418.      Path outer_path,inner_path;
  419.      List keys ;
  420. {
  421.      JoinPath pathnode = RMakeJoinPath();
  422.      
  423.      set_pathtype((Path)pathnode,T_NestLoop);
  424.      set_parent ((Path)pathnode,joinrel);
  425.      set_outerjoinpath (pathnode,(pathPtr)outer_path);
  426.      set_innerjoinpath (pathnode,(pathPtr)inner_path);
  427.      set_pathclauseinfo (pathnode,get_clauseinfo (joinrel));
  428.      set_keys ((Path)pathnode,keys);
  429.      set_pathsortkey ((Path)pathnode,(SortKey)NULL);
  430.      set_joinid((Path)pathnode,LispNil);
  431.      set_outerjoincost((Path)pathnode,(Cost)0 /* NULL */);
  432.      set_p_ordering((Path)pathnode,LispNil);
  433.      set_locclauseinfo((Path)pathnode,LispNil);
  434.  
  435.      if /*when */ ( keys) {
  436.       set_p_ordering ((Path)pathnode,get_p_ordering (outer_path));
  437.      }
  438.      set_path_cost ((Path)pathnode,
  439.             cost_nestloop (get_path_cost (outer_path),
  440.                    get_path_cost (inner_path),
  441.                    get_size( outer_rel),
  442.                    get_size( get_parent(inner_path)),
  443.                    page_size( get_size(outer_rel),
  444.                           get_width(outer_rel)),
  445.                    IsA(inner_path,IndexPath)));
  446.      /* add in expensive function costs -- JMH 7/7/92 */
  447.      set_path_cost(pathnode, 
  448.            (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  449.      return(pathnode);
  450. }
  451.  
  452. /*    
  453.  *        create_mergesort_path
  454.  *    
  455.  *        Creates a pathnode corresponding to a mergesort join between
  456.  *        two relations
  457.  *    
  458.  *        'joinrel' is the join relation
  459.  *        'outersize' is the number of tuples in the outer relation
  460.  *        'innersize' is the number of tuples in the inner relation
  461.  *        'outerwidth' is the number of bytes per tuple in the outer relation
  462.  *        'innerwidth' is the number of bytes per tuple in the inner relation
  463.  *        'outer_path' is the outer path
  464.  *        'inner_path' is the inner path
  465.  *        'keys' are the new keys of the join relation
  466.  *        'order' is the sort order required for the merge
  467.  *        'mergeclauses' are the applicable join/restriction clauses
  468.  *        'outersortkeys' are the sort varkeys for the outer relation
  469.  *        'innersortkeys' are the sort varkeys for the inner relation
  470.  *    
  471.  */
  472.  
  473. /*  .. match-unsorted-inner, match-unsorted-outer, sort-inner-and-outer
  474.  */
  475.  
  476. MergePath
  477. create_mergesort_path (joinrel,outersize,innersize,outerwidth,
  478.                innerwidth,outer_path,inner_path,keys,order,
  479.                mergeclauses,outersortkeys,innersortkeys)
  480.      Rel joinrel;
  481.      Count outersize,innersize,outerwidth,innerwidth;
  482.      Path outer_path,inner_path;
  483.      LispValue keys,order,mergeclauses,outersortkeys,innersortkeys ;
  484. {
  485.      MergePath pathnode = RMakeMergePath();
  486.  
  487.      set_pathtype ((Path)pathnode,T_MergeJoin);
  488.      set_parent ((Path)pathnode,joinrel);
  489.      set_outerjoinpath ((JoinPath)pathnode,(pathPtr)outer_path);
  490.      set_innerjoinpath ((JoinPath)pathnode,(pathPtr)inner_path);
  491.      set_pathclauseinfo ((JoinPath)pathnode,get_clauseinfo (joinrel));
  492.      set_keys ((Path)pathnode,keys);
  493.      set_p_ordering ((Path)pathnode,order);
  494.      set_path_mergeclauses (pathnode,mergeclauses);
  495.      set_locclauseinfo((Path)pathnode,LispNil);
  496.      set_outersortkeys (pathnode,outersortkeys);
  497.      set_innersortkeys (pathnode,innersortkeys);
  498.      set_path_cost ((Path)pathnode, cost_mergesort( get_path_cost (outer_path),
  499.                             get_path_cost (inner_path),
  500.                             outersortkeys,
  501.                             innersortkeys,
  502.                             outersize,
  503.                             innersize,
  504.                             outerwidth,
  505.                             innerwidth));
  506.      /* add in expensive function costs -- JMH 7/7/92 */
  507.      set_path_cost(pathnode, 
  508.            (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  509.      return(pathnode);
  510. }
  511.  
  512. /*    
  513.  *        create_hashjoin_path
  514.  *    
  515.  *        XXX HASH
  516.  *    
  517.  *        Creates a pathnode corresponding to a hash join between two relations.
  518.  *    
  519.  *        'joinrel' is the join relation
  520.  *        'outersize' is the number of tuples in the outer relation
  521.  *        'innersize' is the number of tuples in the inner relation
  522.  *        'outerwidth' is the number of bytes per tuple in the outer relation
  523.  *        'innerwidth' is the number of bytes per tuple in the inner relation
  524.  *        'outer_path' is the outer path
  525.  *        'inner_path' is the inner path
  526.  *        'keys' are the new keys of the join relation
  527.  *        'operator' is the hashjoin operator
  528.  *        'hashclauses' are the applicable join/restriction clauses
  529.  *        'outerkeys' are the sort varkeys for the outer relation
  530.  *        'innerkeys' are the sort varkeys for the inner relation
  531.  *    
  532.  */
  533.  
  534. /*  .. hash-inner-and-outer
  535.  */
  536.  
  537. HashPath
  538. create_hashjoin_path (joinrel,outersize,innersize,outerwidth,
  539.               innerwidth,outer_path,inner_path,keys,operator,
  540.               hashclauses,outerkeys,innerkeys)
  541.      Rel joinrel;
  542.      Count outersize,innersize,outerwidth,innerwidth;
  543.      Path outer_path,inner_path;
  544.      LispValue keys,hashclauses,outerkeys,innerkeys ;
  545.      ObjectId operator;
  546. {
  547.     HashPath pathnode = RMakeHashPath();
  548.  
  549.     set_pathtype ((Path)pathnode,T_HashJoin); 
  550.     set_parent ((Path)pathnode,joinrel);
  551.     set_outerjoinpath ((JoinPath)pathnode,(pathPtr)outer_path);
  552.     set_innerjoinpath ((JoinPath)pathnode,(pathPtr)inner_path);
  553.     set_pathclauseinfo ((JoinPath)pathnode,get_clauseinfo (joinrel));
  554.     set_locclauseinfo((Path)pathnode,LispNil);
  555.     set_keys ((Path)pathnode,keys);
  556.     set_pathsortkey ((Path)pathnode,(SortKey)NULL);
  557.     set_p_ordering((Path)pathnode,LispNil);
  558.     set_outerjoincost((Path)pathnode,(Cost)0);
  559.     set_joinid((Path)pathnode, (Relid)NULL);
  560. /*    set_hashjoinoperator (pathnode,operator);  */ 
  561.     set_path_hashclauses (pathnode,hashclauses);
  562.     set_outerhashkeys (pathnode,outerkeys);
  563.     set_innerhashkeys (pathnode,innerkeys);
  564.     set_path_cost ((Path)pathnode,cost_hashjoin( get_path_cost (outer_path),
  565.                          get_path_cost (inner_path),
  566.                          outerkeys,
  567.                          innerkeys,
  568.                          outersize,innersize,
  569.                          outerwidth,innerwidth));
  570.     /* add in expensive function costs -- JMH 7/7/92 */
  571.     set_path_cost(pathnode, 
  572.           (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)));
  573.     return(pathnode);
  574. }
  575.  
  576.